Many web-based systems use security tokens, such as Security Assertion Markup Language (SAML) tokens, to verify and authenticate users of the system. To obtain a security token, a user provides a credential to a security token service (STS). The STS attempts to authenticate an identity of the user based on the credential. If the STS successfully authenticates the identity of the user, the STS gathers claims from one or more claim providers. The claims can comprise various types of data. For example, the claims can comprise assertions about the identity of the user. After gathering the claims from the claim providers, the STS generates a security token and provides the security token to the user. After receiving the security token, the user provides the security token to the web service for each request it makes to the service. When the web service receives the security token, the web service uses the claims in the security token to determine whether or not the user is authorized to access a resource provided by the web service. These security tokens are expensive to create and can become quite large during an interactive session with the web-based system.